Product Code Database
Solving chess consists of finding an optimal strategy for the game of chess; that is, one by which one of the players (White or Black) can always force either a victory or a draw (see solved game). It is also related to more generally solving chess-like games (i.e. combinatorial games of perfect information) such as Capablanca chess and infinite chess. In a weaker sense, solving chess may refer to proving which one of the three possible outcomes (White wins; Black wins; draw) is the result of two perfect players, without necessarily revealing the optimal strategy itself (see indirect proof).
No complete solution for chess in either of the two senses is known, nor is it expected that chess will be solved in the near future (if ever). Progress to date is extremely limited; there are tablebases of perfect endgame play with a small number of pieces (up to seven), and some Chess variant have been solved at least weakly. Calculated estimates of Game complexity and state-space complexity of chess exist which provide a bird's eye view of the computational effort that might be required to solve the game.
One consequence of developing the seven-piece endgame tablebase is that many interesting theoretical chess endings have been found. The longest seven-piece example is a mate-in-549 position discovered in the Lomonosov tablebase by Guy Haworth, ignoring the 50-move rule. Such a position is beyond the ability of any human to solve, and no chess engine plays it correctly, either, without access to the tablebase, which initially (in 2014) required 140 TB of storage space and the use of a supercomputer but was later reduced down to 18.4 TB through the Syzygy tablebase. As of January 2023, the longest known forced mating sequence for the eight-piece tablebase (also ignoring the 50-move rule) was 584 moves. This was discovered in mid-2022 by Marc Bourzutschky. The eight-piece tablebase is currently incomplete, though, so it is not guaranteed that this is the absolute limit for the eight-piece tablebase.
Some Chess Variant which are simpler than chess have been solved. A winning strategy for Black in Maharajah and the Sepoys can be easily memorised. The 5×5 Gardner's Minichess variant has been Solved game as a draw. Although Losing Chess is played on an 8×8 board, its forced capture rule greatly limits its complexity, and a computational analysis managed to weakly solve this variant as a win for White.
The prospect of solving individual, specific, chess-like games becomes more difficult as the board-size is increased, such as in large chess variants, and infinite chess.
Shannon then went on to estimate that solving chess according to that procedure would require comparing some 10 (Shannon number) possible game variations, or having a "dictionary" denoting an optimal move for each of the approximately 4.8x10 possible board positions. The number of mathematical operations required to solve chess, however, may be significantly different than the number of operations required to produce the entire Game tree of chess. In particular, if White has a forced win, only a subset of the game-tree would require evaluation to confirm that a forced-win exists (i.e. with no refutations from Black). Furthermore, Shannon's calculation for the complexity of chess assumes an average game length of 40 moves, but there is no mathematical basis to say that a forced win by either side would have any relation to this game length. Indeed, some expertly played games (grandmaster-level play) have been as short as 16 moves. For these reasons, mathematicians and game theorists have been reluctant to categorically state that solving chess is an intractable problem. http://www.chessgames.com Magnus Carlsen vs Viswanathlan Anand, King's Indian Attack: Double Fianchetto (A07), 1/2-1/2, 16 moves.
Hans-Joachim Bremermann, a professor of mathematics and biophysics at the University of California at Berkeley, further argued in a 1965 paper that the "speed, memory, and processing capacity of any possible future computer equipment are limited by specific physical barriers: the light barrier, the quantum barrier, and the thermodynamical barrier. These limitations imply, for example, that no computer, however constructed, will ever be able to examine the entire tree of possible move sequences of the game of chess." Nonetheless, Bremermann did not foreclose the possibility that a computer would someday be able to solve chess. He wrote, "In order to have a computer play a perfect or nearly perfect game, it will be necessary either to analyze the game completely ... or to analyze the game in an approximate way and combine this with a limited amount of tree searching. ... A theoretical understanding of such heuristic programming, however, is still very much wanting."
Recent scientific advances have not significantly changed these assessments. The game of English draughts was (weakly) solved in 2007, but it has roughly the square root of the number of positions in chess. Jonathan Schaeffer, the scientist who led the effort, said a breakthrough such as quantum computing would be needed before solving chess could even be attempted, but he does not rule out the possibility, saying that the one thing he learned from his 16-year effort of solving checkers "is to never underestimate the advances in technology".
|
|
